package com.zdp.剑指offer;

public class Main {

    public static void main(String[] args) {
	// write your code here
        Main demo = new Main();
        for(int i=1;i<=50;i++){
            int[]nums = demo.createNums(i+1);
            demo.outNums(nums,i+1);
            int judge = demo.judge(nums, i + 1);
            System.out.println("结果为"+judge);
            System.out.println("=========================length为"+(i+1)+"的数组找重复数结束==========");
        }
    }
    //打印数组
    public void outNums(int[]nums,int length){
        for(int i=0;i<length;i++){
            if(i==0){
                System.out.print("[");
                System.out.print(nums[i]);
            }else{
                System.out.print(","+nums[i]);
            }

        }
        System.out.print("]\n");
    }
    //来一个生成样例
    public int[] createNums(int length){
        int[] nums = new int[length];
        for (int i = 0; i < length; i++) {
            nums[i] =((int)(Math.random()*(length-1)))+1;
        }
        return nums;
    }
    //利用二分法 来实现
    public int judge(int[] nums,int length){
        int start = 1;
        int end = length-1;

        while(start<=end){
            //计算中间值
            int middle = ((end-start)>>1 )+start;
            //计算 在Start-middle 范围的值出现的次数
            int count = getCount(nums,length,start,middle);
            if(start==end){ //说明找到头了
                if(count>1)
                    return start;
            }
            if(count>(middle-start+1))
                end = middle;
            else
                start = middle+1;
        }

        return -1;
    }
    public int getCount(int[] nums,int length,int start,int end){
        int count= 0;
        for(int i=0;i<length;i++){
            if(nums[i]>=start&&nums[i]<=end)
                count++;
        }
        return count;
    }
}
